package com.exercises;


import com.alibaba.fastjson.JSONObject;

class Exercise1269 {
    public static void main(String[] args) {
        System.out.println(new Exercise1269().numWays(27, 7));

    }


    public int numWays(int steps, int arrLen) {
        int modul = (int) Math.pow(10, 9) + 7;
        int maxSize = Math.min(steps + 1, arrLen);
        int[] dp = new int[maxSize];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 1; i < steps; i++) {
            int[] dp2 = new int[maxSize];
            for (int j = 0; j < maxSize; j++) {
                dp2[j] = dp[j];
                if (j > 0) {
                    dp2[j] = (dp2[j] + dp[j - 1]) % modul;
                }
                if (j < maxSize - 1) {
                    dp2[j] = (dp2[j] + dp[j + 1]) % modul;
                }
            }
            dp = dp2;
//            System.out.println(JSONObject.toJSONString(dp));

        }
        return dp[0];
    }
}

